public class Leetcode {
}

//leetcode:474:一和零
class Solution1 {
    public int findMaxForm(String[] strs, int m, int n) {
        int k = strs.length;
        //创建一个dp表，表示前i个元素，中能够凑成m个0和n个1的最大个数
        int[][][] dp = new int[k+1][m+1][n+1];

        for(int i = 1; i <= k; i++){
            //计算每个元素包含一和零的个数
            int a = 0, b = 0;
            for(char ch : strs[i-1].toCharArray()){
                if(ch == '0') a++;
                else b++;
            }

            for(int j = 0; j <= m; j++){
                for(int x = 0; x <= n; x++){
                    //如果不选i位置的元素，就在前i-1个元素去找j个0和x个1的长度
                    dp[i][j][x] = dp[i-1][j][x];
                    //如果选i位置就，判断除去i位置的a个0和b个1后，去前i-1个元素找j-a个0和x-b个1的长度
                    if(j >= a && x >= b){
                        dp[i][j][x] = Math.max(dp[i][j][x] , dp[i-1][j-a][x-b]+1);
                    }
                }
            }
        }
        return dp[k][m][n];
    }
}

//leetcode:879:盈利计划
class Solution2 {
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int len = group.length ,MOD = (int)1e9 + 7;
        //创建一个dp表，表示从前i组成员中挑选，总人数"不超过"j,总利润"不小于"k的所有选法
        int[][][] dp = new int[len+1][n+1][minProfit+1];
        for(int j = 0; j <= n; j++) dp[0][j][0] = 1;

        for(int i = 1; i <= len; i++){
            for(int j = 0; j <= n; j++){
                for(int k = 0; k <= minProfit; k++){
                    //不选第i个组的成员
                    dp[i][j][k] = dp[i-1][j][k];
                    //选第i个组的成员，同时我们要判断选了第i组成员后，要在前i-1组成员中去找人数为j-group[i-1]并且总利润不小于k-profit[i-1]的选法
                    if(j >= group[i-1])
                        //注意如选i位置后k-profit[i-1]的利润是小于0的，我们只需要去找总利润"不小于"0的选法即可，因为我们i位置的值已经达到了所需利润
                        dp[i][j][k] += dp[i-1][j-group[i-1]][Math.max(0,k-profit[i-1])];
                    dp[i][j][k] %= MOD;
                }
            }
        }
        return dp[len][n][minProfit];
    }
}